Computers are used to store and organize data. Stored data may be structured and managed with many objectives, some conflicting. For example, data may be structured and managed for reliability and integrity, efficient reading and writing, efficient searching, minimal waste of the underlying storage, ease of management, minimal computational overhead, and so forth. The particular algorithms and strategies that may be used to structure and manage any particular data often depend on which of these objectives are most important for the use of that data. As discussed below, algorithms and techniques that can improve any of these objectives without significantly undermining other objectives are desirable. Before discussing some shortcomings and improvements in the field of structured data storage, some terminology will be established.
A common data storage scenario involves a storage system layering structured data on an underlying block-based storage unit. There are many kinds of block-based storage units. For instance, disk drives, logical and physical file system volumes, memory, virtualized storage devices, database page files, block-based cloud storage systems, and so forth. Block-based storage units are referred to herein as “storage units”, with the understanding that the term refers to any type of discrete unit of storage, physical or virtual, that is able to store structured data within its discrete blocks, pages, clusters, or other generally segmented into uniform sub-units of storage, which will be referred to herein as “blocks”. Usually, the blocks of a storage unit are contiguous, their size is aligned with the size of their storage unit, and they are discretely written to and read from their storage unit. Note that a block can also be a byte of a byte-addressable storage (DAX).
The term “storage system” is used herein to refer to any computer-executable system that organizes and manages structured data (“data”) within the blocks of a storage unit, where the data is structured for retrieval, updating, deletion, etc., by the storage system. “Structured data” will refer to the data abstraction provided by a storage system and layered on top of a storage unit. Typically, structured data is stored in objects (data types, items, sub-structures, etc.) defined and implemented by the storage system. Objects typically store data that is passed into the storage system (e.g., “user data” or “client data”) as well as management metadata generated and used by the storage system. A storage system usually maintains “storage metadata” on a storage unit to logically arrange the storage unit's objects and perhaps track properties of the objects (i.e., object metadata). Storage systems also store and manage global metadata for a storage unit. A storage unit's global metadata may include data about the storage unit itself, for instance its size (or location and extent), layout, block size, properties, access credentials or keys, global information about the structured data per se, and so forth. For efficiency, global and storage metadata (collectively, “metadata”) are often stored in trees. Often, a root piece of global metadata points to other units of global metadata.
File systems are one type of structured data. In terms of file systems, a file system manager is an example of a storage manager. A volume, whether physical or logical, is an example of a storage unit consisting of blocks (i.e., nodes, clusters, etc.). A file system is an example of structured data managed by a file system manager, which is usually included as part of the storage stack of an operating system. Objects of a file system typically include files, directories, links, access control lists, and others. Storage metadata provides the hierarchical structure of a file system. Global metadata of a file system or volume may include information about which blocks are allocated, counts of references to objects in the file system, the number of blocks and their size, properties of the volume, etc. All of this file system information is overlaid on the blocks of the volume and is managed by the file system manager.
Databases are another type of structured data. In terms of databases, a database engine is an example of storage system. A page file consisting of pages (i.e., blocks) is an example of a storage unit managed by a database engine. A database is an example of structured data overlaid on the pages of the page file, and the objects of a database typically consist of tables, records, indexes, schemas, security information. Global metadata may include information about which pages are allocated, which objects are stored at which locations of which pages, and so forth.
With this terminology in mind, consider that most storage systems allow updating of their structured data; they enable objects to be added, removed, and modified. Therefore, most storage systems have some mechanism for, for a given storage unit, tracking which blocks of the storage unit are currently allocated, i.e., which blocks are in use to store global metadata, storage metadata, objects, object metadata, or any other information. Because allocating blocks, deallocating blocks, and querying for block allocation states are frequent operations of storage systems, a storage system's performance may be limited by how quickly these allocation operations can be performed. For speed, storage systems generally use some form of index (a type of global metadata) to track block allocation states. Recently, trees such as B− trees and B+ trees have been favored due in part to their fast search times and other advantages. In any case, often, the more efficient an index, the more vulnerable the index may be to corruption. For some types of indexes, one erroneous bit might cause a storage system to consider an entire corresponding storage unit to be corrupt and unusable. Described below are techniques for detecting corruption in allocation indexes and repairing corrupt allocation indexes while the related structured data and storage unit remain online and continues to be made available by the corresponding storage system.
Many storage systems also track how many references are currently active for the objects in a storage unit. For instance, a file system may have a tree of reference counts maintained by a file system manager to track how many references are active for objects in the file system. Described below are techniques for monitoring the integrity of global reference counts while corresponding structured data remains online, and, while the structured data remains online, repairing the reference counts in a way that allows the structured data to remain online.
Other techniques for improving the availability and robustness of structured data, in particular storage metadata and global metadata are also described below.